A computer network is a geographically distributed collection of interconnected network links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). End nodes, such as personal computers or workstations, typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, such as a switch or router, having a plurality of ports which may be coupled to the networks. For example, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs at high speed. The switching function includes receiving a data packet at a source port that originated from a source node and transferring that packet to at least one destination port for forwarding to a destination node.
On the other hand, a router may be used to interconnect LANs executing different LAN standards and/or to provide higher level functionality than a switch. If the LAN standards associated with the source and destination nodes are dissimilar (e.g., Ethernet and token ring), the router may also alter the format of the packet so that it may be received by the destination node. Routers typically operate at the network layer of a communications protocol stack used by the network, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISPs equipment. Here, a router may be utilized to interconnect a plurality of private networks to an IP backbone network.
Typically, high-speed input links of the private networks couple to input ports of the router that feed to a single output buffer connected to an output link of the IP backbone network. Depending upon the bandwidths of the input and output links, the incoming data packets may “burst-up” at the output buffer as the packets wait to be transmitted over the shared output link. Moreover, the router may function to aggregate different kinds of packet traffic (e.g., large data packets v. small voice or video packets) over the shared link; in this case, different qualities of service (QoS) may also be required for those packets.
For example, if a small voice packet is loaded into the output buffer behind a large data packet, the voice packet will incur a latency of at least the time needed for the data packet to exit the buffer over the output link. A common objective is to reduce the total end-to-end round trip time for voice packets traversing a network between two end nodes in situations where, e.g., users are conducting a telephone conversation. Some unavoidable delay is incurred when packets traverse the actual network links between the nodes; however, it is possible to reduce packet delay that arises within the routers of the network. One source of delay within a router is the delay incurred at the output buffer (e.g., a queue); an objective of the present invention is to reduce the delay encountered by a packet within a queue structure of an intermediate station, such as a switch or router.
A solution to the QoS issue is to provide a plurality of output queues at the router, where each queue is dedicated to a particular data type. For example, a relatively large queue may be provided for data traffic so that the “data” queue can accommodate bursts of data as provided by, e.g., file transfer protocol transfers. In contrast, relatively small output queues may be allocated for voice and video traffic forwarded through the router. Yet, each of these output queues require access to a single resource, e.g., the output link. Accordingly, a scheduler function may be employed within the router to service the queues in an ordered manner according to the types of traffic and the QoS policies governing the relationships between these types of traffic.
One type of scheduler utilized in packet-based switches and/or routers is a link sharing queue scheduler that multiplexes the packets stored in a number of output queues onto a shared media link in a configurable manner that provides fairness and weighted relative priority. Examples of link sharing algorithms executed by the scheduler include weighted fair queuing (WFQ), weighted round robin (WRR), deficit round robin (DRR) and modified deficit round robin (MDRR). The WFQ algorithm is characterized by the assignment of relative weights to the each of the output queues that share the bandwidth of a single output link. When these output queues are not empty, they are serviced such that the total bandwidth of the output link is apportioned among the relative weighted ratios of the queues. WRR is an algorithm that implements weighted queuing in a fair, round robin manner.
The DRR algorithm assigns each queue a quantum of work and enforces bandwidth rates such that each output queue delivers its proportion of a maximum transfer unit with respect to the total bandwidth of the output link. The DRR algorithm further ensures that each of the output queues is serviced fairly with respect to each other. A problem with this algorithm is that if one of the queues is configured to store voice packets whose actual bandwidth is small relative to the total bandwidth of the output link, substantial delays may be incurred by those packets when fairly servicing the voice queue with respect to the other output queues.
The MDRR algorithm operates to provide priority service to such a “delay-sensitive” queue while maintaining typical DRR service for the remaining queues. One implementation of the MDRR algorithm is a strict priority implementation that always services a low latency queue before servicing the remaining queues. Disadvantages of this implementation include (i) the potential to “starve out” the remaining queues and (ii) a limitation of one low latency output queue, i.e., the MDRR algorithm does not allow the flexibility to define more than one low latency queue for a strict priority implementation.
A further implementation of weighted link sharing involves utilization of the entire bandwidth of the output link in the presence of any non-empty output queues. Specifically, if one queue in a weighted link-sharing environment is not being used, the bandwidths of the remaining queues increase but at a rate that is proportional to their relative weights. This implementation of weighted link sharing is referred to as a work conserving implementation. Another class of schedulers, known as non-work conserving schedulers, may not transmit a packet even if one is waiting to be serviced. Although work conserving schedulers produce lower delays and lower packet loss ratios, non-work conserving schedulers have the capability to perform traffic shaping. Traffic shaping schedulers smooth the transmission of packets from an output queue at a configured bit rate in a generally non-work conserving manner.
Some conventional packet-based switches and routers include traffic shaping and link sharing functions, wherein the traffic shaping function enforces a configurable maximum bit rate on a link or queue to complement the weighted minimal share guaranteed by the link sharing function. These routers generally implement traffic shaping as a function independent of link sharing, either in software, e.g., as separate functional blocks downstream from one another, or in hardware, e.g., as separate functional mechanisms associated with levels of a queuing subsystem cascaded as a hierarchy of queues, typically within an application specific integrated circuit (ASIC). The queuing subsystem may comprise a multi-level structure that includes a top level of queues associated with a link sharing mechanism coupled to an intermediate level of queues associated with a traffic shaping mechanism. However, the hardware implementation of separate functional mechanisms associated with the queuing subsystem consumes substantial “real estate” on the ASIC and typically employs a feedback mechanism from the intermediate level to the top level of queues to, e.g., enforce bandwith consumption requirements. The software implementation of separate functional blocks, on the other hand, is generally complicated and consumes substantial processor resources on the routers.
Multi-level queuing structures are also often present in switches and routers that implement class-based queuing (CBQ). CBQ techniques require a plurality of queuing functions (e.g., enqueue and dequeue operations) at each level of the cascading hierarchy of queues, resulting in higher implementation costs for a given performance level. Because of the latency associated with these functions, forwarding performance of the router degrades rapidly as the number of queues is increased. This tends to limit the router to a small number of queues per interface, which, in turn, limits the services available through each interface.
Accordingly, it is desirable to provide a technique that supports common queuing and queue service disciplines within a framework that is sufficiently simple and compact for implementation in a hardware (ASIC) forwarding engine.